package com.company.ljh.easy;

/**
 * @description:
 * 1071. 字符串的最大公因子
 * 提示
 * 简单
 * 306
 * 相关企业
 * 对于字符串 s 和 t，只有在 s = t + ... + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
 *
 * 给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。
 * @projectName:leet_code
 * @see:com.company.ljh.easy
 * @author:ljh
 * @createTime:2023/6/29 10:47
 * @version:1.0
 */
public class 字符串最大公因数 {
    /** 解法一：从左开始的字符串即为当前字符串因子，从最长因子开始遍历**/
    public String gcdOfStrings(String str1, String str2) {
        String shortStr = "";
        String longStr = "";
        if(str1.length() < str2.length()){
            shortStr = str1;
            longStr = str2;

        }else{
            shortStr = str2;
            longStr = str1;
        }
        int index = shortStr.length();
        while(index > 0){
            String gcd = shortStr.substring(0,index--);
            if(checkIsGcd(shortStr,gcd)&&checkIsGcd(longStr,gcd)){
                return gcd;
            }
        }
        return "";
    }
    public boolean checkIsGcd(String str,String gcd){
        int strIndex = 0;
        int gcdIndex = 0;
        while(strIndex < str.length()){
            if(str.charAt(strIndex++) != gcd.charAt(gcdIndex++)){
                return false;
            }
            if(gcdIndex >=gcd.length() ){
                gcdIndex = 0;
            }
        }
        if(gcdIndex == 0)
            return true;
        return false;
    }
    /**2.最大公约数法，两个字符串最大组成子串长度一定是两个字符串长度的最大公因数，使用辗转相除发求的最大公因数，判断是否为组成子串即可**/

    /** 3.字符串交替合并法，如果两个字符串有最大共因数，那么a+b 和b+a 是相同的**/
}
